package com.LeeCode;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

/**
 * 距离最小相等元素查询
 */

public class Code3488 {
    public static void main(String[] args) {
        int[] nums = {1, 2, 3, 4};
        int[] queries = {0, 1, 2, 3};
        System.out.println(new Code3488().solveQueries(nums, queries));
    }

    public List<Integer> solveQueries(int[] nums, int[] queries) {
        List<Integer> ans = new ArrayList<>();
        HashMap<Integer, List<Integer>> map = new HashMap<>();
        int len = nums.length;
        // 存储每个元素对应的下标
        for (int i = 0; i < nums.length; i++) {
            if (!map.containsKey(nums[i])) {
                map.put(nums[i], new ArrayList<>());
            }
            map.get(nums[i]).add(i);
        }

        for (int index : queries) {
            int query = nums[index];
            List<Integer> list = map.get(query);
            if (list == null || list.size() == 1) {
                ans.add(-1);
                continue;
            }
            // 相同的数字不止一个
            int pos = lowerBound(list, index), minDist;
            // 该查询的前后两个元素位置
            int before = (pos - 1 + list.size()) % list.size(), after = (pos + 1) % list.size();
            int p1 = Math.min(list.get(pos), list.get(before));
            int p2 = Math.max(list.get(pos), list.get(before));

            minDist = Math.min(p2 - p1, p1 + len - p2);

            // 若前后元素不重叠
            if (before != after) {
                p1 = Math.min(list.get(pos), list.get(after));
                p2 = Math.max(list.get(pos), list.get(after));
                int temp = Math.min(p2 - p1, p1 + len - p2);
                minDist = Math.min(temp, minDist);
            }
            ans.add(minDist);

        }
        return ans;
    }

    // 开区间二分查找
    private int lowerBound(List<Integer> list, int target) {
        int left = -1, right = list.size(), mid;
        while (left + 1 < right) {
            mid = left + (right - left) / 2;
            if (list.get(mid) >= target) {
                right = mid;
            } else {
                left = mid;
            }
        }
        return right;
    }
}
